package arithmetic;

//import sun.rmi.runtime.Log;

import java.awt.event.KeyAdapter;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;

/**
 * @Author: Jie
 * @Date: 2019/1/15 10:53
 * @Function :优先队列
 * 按照优先级，出队
 *
 * 实现机制：
 * 1、heap（Binary，Binomial，Fibonacci）
 * 堆
 * eg: min Heap,Max Heap
 *
 *  2、Binary Searc Tree-二叉搜索树
 *
 *  leetcode:703  数据流中的第K大元素
 *  https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/
 *
 *  分析：
 *  方法1： 保存前K个最大值。
 *  1、排序前K
 *  N * kLogK(排序)
 *
 *  方法2；优先队列数据结构 Min Heap  且 Size == k
 *  eg：
 *      4
 *    5   8
 * 进行N 次运算*（1 or log2k)  --log底为2
 *  平均 N* log2k-- log底为2
 */
public class A_05_PriorityQueue {
    public static void main(String[] args) {
        KthLargest kthLargest = new KthLargest(3, new int[]{4, 5, 8, 2});
        System.out.println(kthLargest.add(3));
        System.out.println(kthLargest.add(5));
        System.out.println(kthLargest.add(10));
        System.out.println(kthLargest.add(9));
        System.out.println(kthLargest.add(4));

        PriorityQueue<Integer> mQueue = new PriorityQueue<>(3);
        mQueue.add(3);
        mQueue.add(4);
        mQueue.add(2);
        mQueue.add(1);

        System.out.println("A_05_PriorityQueue:main:mQueue.poll:"+mQueue.poll());

//        System.out.println("remove obj=="+mQueue.remove(Integer.valueOf((2))));
//        customMaxHeap();
    }

    private static void customMaxHeap() {
        //是用 自定义的compare
        PriorityQueue<People> queue = new PriorityQueue<People>(5,
                new Comparator<People>() {
                    public int compare(People p1, People p2) {
//                        return p2.age - p1.age;//Max heap
                        return p1.age - p2.age;//Min heap
                    }
                });

        for (int i = 1; i <= 10; i++) {
//            queue.add(new People("张"+ i, (new Random().nextInt(100))));
            People people = new People("张" + i, (new Random().nextInt(100)));
            queue.add(people);
            System.out.println("add..."+people.toString());
        }
        System.out.println("***********************");
        while (!queue.isEmpty()) {
            System.out.println(queue.poll().toString());
        }
    }
}

class KthLargest {

    //PriorityQueue默认是一个小顶堆，可以通过传入自定义的Comparator函数来实现大顶堆
    private  PriorityQueue<Integer> queue;
    private  int k;
    public KthLargest(int k, int[] nums) {
        this.k = k;
        queue = new PriorityQueue<>(k, new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        for (int num:nums) {
            add(num);
        }
    }

    public int add(int val) {
        if (queue.size()<k){
            queue.add(val);
        }else if (val>queue.peek()){
            queue.poll();
            queue.offer(val);
        }
        return queue.peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

class People {
    String name;
    int age;
    public People(String name, int age){
        this.name = name;
        this.age = age;
    }
    public String toString() {
        return "姓名："+name + " 年龄：" + age;
    }
}